package com.arron.algorithm.leetcodetop100.技巧.摩尔投票;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 *  摩尔投票详解
 *  https://leetcode.cn/problems/majority-element-ii/solutions/1/liang-fu-dong-hua-yan-shi-mo-er-tou-piao-fa-zui-zh/
 */
public class 多数元素II {



    public List<Integer> majorityElement(int[] nums) {

        if (nums.length == 1){
            return Collections.singletonList(nums[0]);
        }


        int len = nums.length;
        int cd1 = nums[0];
        int cd2 = nums[0];

        int count1 = 0;
        int count2 = 0;
        // 3,2,3
        for (int j : nums) {


            if (j == cd1) {
                count1++;
                continue;
            }

            if (j == cd2) {
                count2++;
                continue;
            }

            if (count1 == 0) {
                cd1 = j;
                count1 = 1;
                continue;
            }

            if (count2 == 0) {
                cd2 = j;
                count2 = 1;
                continue;
            }
            count1--;
            count2--;

        }

        count1=0;
        count2=0;
        //最后对候选人进行统计票数，防止没有超过n/3的元素，候选人全部被抵消的情况
        for (int num : nums) {

            if (cd1 == num) {
                count1++;
                //这里必须是else if，因为cd1,cd2的初始化是相同的数，同理上个for循环为什么用 continue 也是如此
            } else if (cd2 == num) {
                count2++;
            }
        }
        List<Integer> res = new ArrayList<>();

        if (count1> len/3) {
            res.add(cd1);
        }
        if (count2> len/3) {
            res.add(cd2);
        }
        return res;
    }

}
